package com.sheng.leetcode.year2022.month09.day23;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/23
 *<p>
 * 707. 设计链表<p>
 *<p>
 * 设计链表的实现。您可以选择使用单链表或双链表。<p>
 * 单链表中的节点应该具有两个属性：val和next。val是当前节点的值，<p>
 * next是指向下一个节点的指针/引用。如果要使用双向链表，<p>
 * 则还需要一个属性prev以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。<p>
 * 在链表类中实现这些功能：<p>
 * get(index)：获取链表中第index个节点的值。如果索引无效，则返回-1。<p>
 * addAtHead(val)：在链表的第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点。<p>
 * addAtTail(val)：将值为val 的节点追加到链表的最后一个元素。<p>
 * addAtIndex(index,val)：在链表中的第index个节点之前添加值为val 的节点。如果index等于链表的长度，<p>
 *      则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。<p>
 * deleteAtIndex(index)：如果索引index 有效，则删除链表中的第index 个节点。<p>
 *<p>
 * 示例：<p>
 * MyLinkedList linkedList = new MyLinkedList();<p>
 * linkedList.addAtHead(1);<p>
 * linkedList.addAtTail(3);<p>
 * linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3<p>
 * linkedList.get(1);            //返回2<p>
 * linkedList.deleteAtIndex(1);  //现在链表是1-> 3<p>
 * linkedList.get(1);            //返回3<p>
 *<p>
 * 提示：<p>
 *<p>
 * 所有val值都在[1, 1000]之内。<p>
 * 操作次数将在 [1, 1000]之内。<p>
 * 请不要使用内置的 LinkedList 库。<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/design-linked-list">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0707 {

    @Test
    public void test01() {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtIndex(1,0);
        System.out.println(linkedList.get(0));
//        MyLinkedList linkedList = new MyLinkedList();
//        linkedList.addAtHead(1);
//        linkedList.addAtTail(3);
//        // 链表变为1-> 2-> 3
//        linkedList.addAtIndex(1,2);
//        // 返回2
//        System.out.println(linkedList.get(1));
//        // 现在链表是1-> 3
//        linkedList.deleteAtIndex(1);
//        // 返回3
//        System.out.println(linkedList.get(1));

//        // 现在链表是2-> 3
//        linkedList.deleteAtIndex(0);
//        // 返回2
//        System.out.println(linkedList.get(0));
    }
}
class MyLinkedList {
    int size;
    ListNode head;

    public MyLinkedList() {
        size = 0;
        head = new ListNode();
    }

    /**
     * 获取链表中第index个节点的值。如果索引无效，则返回-1。
     *
     * @param index 索引
     * @return 索引对应的返回值
     */
    public int get(int index) {
        ListNode pre = head;
        if (index < size) {
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            return pre.val;
        }
        // 索引无效
        return -1;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    /**
     * 在链表中的第index个节点之前添加值为val 的节点。如果index等于链表的长度，
     * 则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
     *
     * @param index 索引
     * @param val 要插入的值
     */
    public void addAtIndex(int index, int val) {
        // index 大于链表长度，不插入
        if (index > size) {
            return;
        }
        if (index == 0) {
            // 插入头结点
            ListNode node = new ListNode(val);
            node.next = head;
            head = node;
        } else if (index == size) {
            // 插入尾节点
            ListNode pre = head;
            for (int i = 0; i < size - 1; i++) {
                pre = pre.next;
            }
            pre.next = new ListNode(val);
        } else {
            // 插入索引的前一个位置
            ListNode node = new ListNode(val);
            ListNode pre = head;
            for (int i = 0; i < index - 1; i++) {
                pre = pre.next;
            }
            node.next = pre.next;
            pre.next = node;
        }
        size++;
    }

    /**
     * 如果索引index 有效，则删除链表中的第index 个节点。
     *
     * @param index 索引
     */
    public void deleteAtIndex(int index) {
        // 判断索引是否有效
        if (index < size) {
            // 链表长度为1时
            if (size == 1) {
                head = new ListNode();
            } else if (index == 0) {
                // 删除头结点
                head = head.next;
            } else {
                // 删除对应位置的结点
                ListNode pre = head;
                for (int i = 0; i < index - 1; i++) {
                    pre = pre.next;
                }
                pre.next = pre.next.next;
            }
            size--;
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
